package com.googlecode.gaal.suffix.impl;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.suffix.algorithm.api.ChildTableBuilder;
import com.googlecode.gaal.suffix.algorithm.api.LcpTableBuilder;
import com.googlecode.gaal.suffix.algorithm.api.SuffixTableBuilder;
import com.googlecode.gaal.suffix.algorithm.impl.ExtendedLcpTableBuilderImpl;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree.BinaryNode;
import com.googlecode.gaal.suffix.api.EnhancedSuffixArray;

public abstract class AbstractBinaryIntervalTree<T extends BinaryNode<T>> extends AbstractIntervalTree<T> implements
        BinaryIntervalTree<T> {

    protected final int[] extendedLcpTable;
    protected final int[] childTable;

    public AbstractBinaryIntervalTree(IntSequence sequence, int alphabetSize, int[] suffixTable, int[] lcpTable,
            int[] extendedLcpTable, int[] childTable) {
        super(sequence, alphabetSize, suffixTable, lcpTable);
        this.extendedLcpTable = extendedLcpTable;
        this.childTable = childTable;
    }

    public AbstractBinaryIntervalTree(IntSequence sequence, int alphabetSize, SuffixTableBuilder suffixTableBuilder,
            LcpTableBuilder lcpTableBuilder, ChildTableBuilder childTableBuilder) {
        super(sequence, alphabetSize, suffixTableBuilder, lcpTableBuilder);
        int[] childTable = childTableBuilder.buildChildTable(lcpTable);
        EnhancedSuffixArray esa = new EnhancedSuffixArrayBase(sequence, alphabetSize, suffixTable, lcpTable, childTable);
        extendedLcpTable = new ExtendedLcpTableBuilderImpl().buildExtendedLcpTable(esa);
        this.childTable = childTableBuilder.buildChildTable(extendedLcpTable);
    }

    @Override
    public int[] getExtendedLcpTable() {
        return extendedLcpTable;
    }

    @Override
    public int[] getChildTable() {
        return childTable;
    }

    @Override
    public Iterator<T> preorderIterator() {
        return new PreorderIterator<T>(top());
    }

    @Override
    public T search(IntSequence pattern) {
        return search(pattern, top(), 0);
    }

    @Override
    public T longestSearch(IntSequence pattern) {
        return search(pattern, top(), null, 0);
    }

    protected T search(IntSequence pattern, T interval, int i) {
        if (interval.isTerminal()) {
            return null;
        }

        int mid = interval.middle();

        // Consume pattern up to the next lcp level.
        for (; i < lcpTable[mid] && i < pattern.size(); i++) {
            if (pattern.get(i) != sequence.get(suffixTable[mid] + i)) {
                return null;
            }
        }

        // After consuming from pattern, check to see if any remaining
        if (i == pattern.size()) {
            return interval;
        }

        if (pattern.get(i) < sequence.get(suffixTable[mid] + i)) {
            return search(pattern, interval.leftChild(), i);
        } else {
            return search(pattern, interval.rightChild(), i);
        }

    }

    protected T search(IntSequence pattern, T interval, T parent, int i) {
        if (interval.isTerminal()) {
            return parent;
        }

        int mid = interval.middle();

        // Consume pattern up to the next lcp level.
        int lcp = lcpTable[mid];
        for (; i < lcp && i < pattern.size(); i++) {
            if (pattern.get(i) != sequence.get(suffixTable[mid] + i)) {
                return parent;
            }
        }

        // After consuming from pattern, check to see if any remaining
        if (i == pattern.size()) {
            return interval;
        }

        if (lcp > (parent == null ? 0 : parent.lcp())) {
            parent = interval;
        }

        if (pattern.get(i) < sequence.get(suffixTable[mid] + i)) {
            return search(pattern, interval.leftChild(), parent, i);
        } else {
            return search(pattern, interval.rightChild(), parent, i);
        }

    }

    protected abstract class AbstractBinaryInterval extends AbstractInterval {

        protected AbstractBinaryInterval(int left, int right) {
            super(left, right);
        }

        @Override
        public int lcp() {
            if (left == right)
                return -1;
            else
                return lcpTable[middle(left, right)];
        }

        public int middle() {
            return middle(left, right);
        }

        protected int middle(int left, int right) {
            if (isTerminal()) {
                throw new UnsupportedOperationException("terminal intervals have no middle");
            }
            int mid = childTable[left];
            if (mid <= left || mid > right) {
                mid = childTable[right];
            }
            return mid;
        }
    }

    protected static class PreorderIterator<T extends BinaryNode<T>> implements Iterator<T> {
        private final Deque<T> stack = new ArrayDeque<T>();
        private T next;

        public PreorderIterator(T top) {
            next = top;
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public T next() {
            if (next == null)
                throw new NoSuchElementException();
            T node = next;
            if (!next.isTerminal()) {
                stack.push(next);
                next = next.leftChild();
            } else if (!stack.isEmpty()) {
                next = stack.pop().rightChild();
            } else {
                next = null;
            }
            return node;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
